\documentclass[a4paper,spanish] {article}
\usepackage [spanish] {babel}
\usepackage [latin1]{inputenc}
\usepackage{graphicx}
\usepackage{caratula}
\usepackage{subfig}
\usepackage{dsfont}
\usepackage{algorithm}
\usepackage{amsmath}
\usepackage{algorithmic}
\usepackage{sidecap}
\usepackage{slashbox}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\pagestyle{empty}

\newcommand{\real}{\ensuremath{\mathbb{R}}}


\parindent = 0 pt
\parskip = 11 pt

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\pagestyle{empty}

%links
\usepackage{hyperref}
\hypersetup{
    colorlinks,%
    citecolor=blue,%
    filecolor=blue,%
    linkcolor=blue,%
    urlcolor=blue
}


\addtolength{\oddsidemargin}{-1in}
\addtolength{\textwidth}{2in}


\begin{document}
\pagestyle{headings}



\newpage

\materia{Sistemas Operativos}
\submateria{Primer Cuatrimestre del 2013}
\titulo{Pthreads: Battlesystem }

\integrante{Gonzalo Fuentes Bahamondes}{412/10}{ness00@gmail.com}
\integrante{Helen Lizana}{118/08}{hsle.22@gmail.com}
\integrante{Gabriel Astorgano}{467/10}{astorsk81991@hotmail.com}

\maketitle


\newpage
\tableofcontents
\newpage

\newpage

\section{Introducci\'on }

Este trabajo pr\'actico se enfoca en multithreading y su control mediante sem\'aforos.

\section{Read-Write Lock}
Para esta instancia, se nos pide implementar un sistema de \emph{Read-Write Lock} utilizando sem\'aforos POSIX, y que el mismo est\'e libre de inanici\'on. Adem\'as, se debe respetar una interfaz propuesta por la c\'atedra. 
Para esta tarea, primero utilizamos una estructura interna llamada \emph{Lightswitch} para resolver algunos problemas de concurrencia. Esta estructura contiene:

\begin{itemize}
   \item Un contador interno.
   \item Un mutex POSIX interno llamado mutex ls.
   \item Un m\'etodo Lock y su contraparte Unlock. Estos m\'etodos reciben un sem\'aforo externo como par\'ametro.
\end{itemize}

El Lightswitch est\'a pensado para convivir con otro sem\'aforo en el sistema y bloquear distintos tipos de acceso a la secci\'on cr\'itica. La estructura se inicia con su contador interno en 0 y su mutex habilitado. Al llamar a lock (con otro sem\'aforo como par\'ametro), se pide el mutex interno del Lightswitch. Una vez obtenido, se aumenta el contador interno en uno, llevando registro de cuantos accesos del mismo tipo est\'an entrando a la secci\'on cr\'itica. Se verifica este valor: Si es 1, este acceso es el primero de este tipo en entrar, por lo que es su responsabilidad pedir Lock del sem\'aforo pasado como par\'ametro, bloqueando de esta forma accesos del otro tipo. Luego, se libera el mutex interno. Los siguientes accesos del tipo actual simplemente incrementan el contador interno en 1 y no piden otro Lock. 

Al pedir Unlock, se hace el proceso inverso: Se pide el mutex interno para modificar el contador interno, restando 1 a su valor. Si el valor es 0, \'este es el \'ultimo acceso pendiente de este tipo, por lo que es su responsabilidad llamar a Unlock del sem\'aforo trabado previamente al llamar a Lock. Luego, se libera el mutex interno. Los anteriores accesos que salen del sistema simplemente decrementan el contador interno en 1 y no realizan otro Unlock.

Por otro lado, la estructura superior RWLock contiene:

\begin{itemize}
   \item Un Lightswitch ls.
   \item Dos mutex POSIX: roomEmpty y turnstile.
   \item Los m\'etodos pre-definidos rlock, runlock, wlock, wunlock.
\end{itemize}


La estructura RWLock intenta resolver dos problemas de concurrencia. El primero es permitir un tipo de accesos (lectura o escritura) bloqueando el otro. El segundo es permitir que haya m\'as de una instancia de un tipo de acceso dado y evitar la concurrencia. Estos problemas son resueltos en su mayor parte por el Lightswitch interno.
\newpage
Al llamar a wlock, se pide lock del mutex turnstile, y una vez obtenido, se pide lock del mutex roomEmpty. De esta forma, un escritor bloquea a los lectores, que deben esperar el mutex turnstile para avanzar. Al llamar a wunlock, se destraba el mutex turnstile y luego el mutex roomEmpty, permitiendo pasar a un lector o escritor y avisando que no hay nadie leyendo la secci\'on cr\'itica.

Como contraparte, al llamar a rlock primero se pide el mutex turnstile y se lo destraba una vez obtenido. Esto permite que los lectores se habiliten uno tras otro, pero que un escritor los trabe si as\'i lo desea. Luego, se invoca al m\'etodo lock del Lightswitch ls, bloqueando al mutex roomEmpty. Al hacer esto, los lectores bloquean a los escritores, que buscan que el mutex roomEmpty est\'e disponible. Al finalizar la lectura, se llama a runlock, llamando a unlock del Lightswitch ls, asegur\'andose que el \'ultimo lector habilite el mutex roomEmpty. 

Con este bloqueo opuesto entre lectores y escritores se soluciona el problema de permitir solo un tipo de acceso, sea lectores o escritores, a la vez. Y, simultaneamente, como el Lightswitch lleva la cuenta de cuantos procesos del mismo tipo ingresan y egresan de la secci\'on cr\'itica, tenemos la seguridad de que el primero bloquee a los accesos del tipo opuesto y el \'ultimo los habilite.

Queda pendiente, entonces, el problema de la posible inanici\'on: Que al entrar un tipo de acceso, el otro tipo se bloquee indefinidamente porque contin\'uan llegando procesos del tipo habilitado. Sin embargo, esto es solucionado por la implementaci\'on de los m\'etodos de RWLock:

Supongamos que arrivan accesos de lectura constantemente. Al llegar cada acceso de lectura, se traba el mutex turnstile y se lo libera una vez obtenido, por lo que el siguiente acceso de lectura no es detenido. Adem\'as, el primer acceso de lectura trab\'o el mutex roomEmpty. Al llegar un escritor, este pide el mutex turnstile, y una vez obtenido, no lo devuelve, por lo que no entra ning\'un lector adicional luego de \'esto, acotando el n\'umero de lectores a la cantidad actual de lectores esperando el Lightswitch ls. Los lectores se turnan entre s\'i con el Lightswitch ls, y luego de que el \'ultimo finaliza su lectura, se libera el mutex roomEmpty, por lo que el escritor logra finalmente escribir.

Ahora, supongamos que un lector es bloqueado por los escritores. El lector pide el mutex turnstile, eventualmente deteniendo a los escritores y avanzando en su ejecuci\'on. Luego, devuelve el mutex turnstile y procede a pedir Lock del Lightswitch ls, bloqueando roomEmpty. Al llegar a esta instancia, si se obtiene el mutex roomEmpty, se bloquean todos los procesos de escritura, ya que los escritores esperan a este mutex. De esta forma, se evita la inanici\'on.

En ambos casos, como ambos tipos de acceso esperan el mutex turnstile, existe el problema de a qui\'en le es asignado este mutex cuando se libera. Pero debido a la implementaci\'on de los sem\'aforos POSIX, podemos asumir que es una implementaci\'on \emph{fair}, y que, por lo tanto, a todo proceso encolado en la espera de este mutex eventualmente lo recibir\'a cuando alguno de los procesos lo libere.
\newpage
Finalmente, ejecutamos dos tests para probar este sistema. El primero consiste en un buffer de cinco int. Generamos cinco threads que leen los cinco int y los imprimen por pantalla. Esto se repite 20 veces, con un tiempo aleatorio de espera para cada thread. Al leer, se pide un read-lock. Una vez generados los cinco thread, se empieza a modificar el buffer, aumentando los valores en 1 y anunci\'andolo por pantalla. Esto se modifica 15 veces, con un tiempo aleatorio de espera. Al escribir, se pide un write-lock. Al ejecutar el test, se puede ver que no ocurre que alguno de los threads de lectura obtiene un buffer con una escritura interrumpida (los n\'umeros son correlativos y siempre aumentan en 1). Esto nos dice que los lectores bloquean correctamente al escritor. Adem\'as, se ve que el escritor logra modificar los datos a pesar de los constantes intentos de leerlo, por lo que tampoco se genera inanici\'on.


El segundo test consiste en 5 procesos que representan un delivery de bebidas. A cada uno se le asignan 30 botellas. Cada vez que se ejecutan, se entrega una botella y disminuye su cantidad de botellas restantes en 1. Adem\'as, como los vendedores son muy deshonestos, puede que aleat\'oriamente tomen algunas de las botellas que tendr\'ian que entregar. Por lo tanto, la empresa decidi\'o crear un sistema que verifica cuantas botellas son entregadas a los clientes y cuantas le quedan a cada vendedor para verificar su integridad. Los reportes son los lectores, y los vendedores, los escritores. En los test se puede ver que los reportes se ejecutan en conjunto con los vendedores, pero que todav\'ia no pueden decidir cuantas botellas se perdieron hasta que no se entreguen todas. Si bien hay varios escritores y \'estos se ejecutan m\'as frecu\'entemente que los lectores, no se genera inanici\'on.
\newpage
\section{Servidor Backend}



\end{document}